Đường này hình thành khi người Pháp xây dựng ga xe lửa Sài Gòn. Ban đầu đường tạm thời được gọi là rue Latérale Sud de la Gare (đường phía nam nhà ga), đến năm 1917 khi nhà ga đi vào hoạt động thì đường được đặt tên là rue Colonel Grimaud.[5]

Năm 1955, đường được đổi tên thành đường Phạm Ngũ Lão, tên gọi này được giữ nguyên đến hiện tại[5]. Thời Việt Nam Cộng hòa, đường Phạm Ngũ Lão còn được gọi là "phố báo chí" của Sài Gòn, do nằm dọc theo con đường tại khu vực này lúc bấy giờ có nhiều tòa soạn của các nhật báo, tuần báo, tạp chí và cả nhà xuất bản, phát hành, nhà in[6]. Khu vực các đường Phạm Ngũ Lão, Đề Thám và Bùi Viện còn có tên gọi là "Ngã tư quốc tế".[7][8]

Năm 1978, chính quyền Thành phố Hồ Chí Minh quyết định di dời ga Sài Gòn về Quận 3, khu vực nhà ga cũ được cải tạo thành công viên 23 tháng 9 như hiện nay.[9]